1. Field of the Invention
This invention relates to network computing systems, and more particularly to replicating data in networks including peer-to-peer networks.
2. Description of the Related Art
Peer-to-Peer Networking
The term peer-to-peer networking or computing (often referred to as P2P) may be applied to a wide range of technologies that greatly increase the utilization of information, bandwidth, and computing resources in the Internet. Frequently, these P2P technologies adopt a network-based computing style that neither excludes nor inherently depends on centralized control points. In addition to improving the performance of information discovery, content delivery, and information processing, such a style also can enhance the overall reliability and fault-tolerance of computing systems.
FIGS. 1A and 1B are examples illustrating the peer-to-peer model. FIG. 1A shows two peer devices 104A and 104B that are currently connected. Either of the two peer devices 104 may serve as a client of or a server to the other device. FIG. 1B shows several peer devices 104 connected over the network 106 in a peer group. In the peer group, any of the peer devices 104 may serve as a client of or a server to any of the other devices.
JXTA
JXTA technology is a set of open protocols that allow any connected device on the network ranging from cell phones and wireless PDAs to PCs and servers to communicate and collaborate in a P2P manner. JXTA peers create a virtual network where any peer can interact with other peers and resources directly even when some of the peers and resources are behind firewalls and NATs (Network Address Translators) or are on different network transports. In JXTA, every peer is identified by an ID (identifier), unique over time and space. Peer groups are user-defined collections of entities (peers) that share a common interest. Peer groups are also identified by unique IDs. Peers can belong to multiple peer groups, can discover other entities and peer resources (e.g. peers, peer groups, services, content, etc.) dynamically and can also publish themselves and resources so that other peers can discover them.
Distributed Computing Systems
In a distributed computing environment, code (e.g. an application, applet, servlet, executable code fragment, or any other computer-executable code) on one machine or virtual machine (e.g. Java Virtual Machine (JVM)) can be distributed to and run on different machines and/or on different virtual machines (e.g. JVMs).
A distributed computing environment may provide a framework for large computational tasks that can be split over a large number of nodes and run in parallel. For instance, a Monte-Carlo simulation may take several months to run. Monte-Carlo simulations can typically be split into several thousands of tasks and run in parallel over a large number of computing nodes. A database may be used to keep track of the tasks that have not been sent to computing nodes for execution, the tasks that have already been submitted to computing nodes, and the tasks that have completed and for which the results are available.
Conventional distributed computing systems such as SETI@Home, described below, may utilize a centralized server to distribute and post-process tasks over the network. This can create reliability and efficiency issues if the centralized server is not working properly or is bogged down, or if the network connections to the centralized server are lost. In a worst-case scenario, if the centralized server fails, the framework goes down and all the tasks and results may be lost.
SETI@Home is an exemplary distributed computing application that enables a large computational job to be executed over several thousands of nodes. The large computational job can be split into many tasks, which are run independently of each other on individual computing nodes. In the SETI@Home project, data from astronomical measurements is farmed out over the Internet to many processors for processing, and when completed returned to a centralized server and post-processed, in an attempt to aid in the detection of alien species. The tasks all reside in a central database and are sent one by one by the centralized server to the individual computing nodes. When the server has sent a task to a computing node, it marks the task as “submitted” in its database, the prior state being “non-submitted”. Once a computing node has completed its assigned task, it sends the result of the execution back to the centralized server, which stores it in its database. The task is then marked “completed”. If too many nodes contact the centralized server, the server becomes a limiting factor in the scalability of the entire system. Further, reliability and efficiency of the system is affected if the centralized server is not working properly or is bogged down, or if the network connections to the centralized server are lost.
Note that such reliability and efficiency problems in systems with a single centralized server for a database are not unique to distributed computing systems.
Distributed Databases
One conventional solution to the reliability and efficiency problems created by having a single centralized server for a database, for example a database in a distributed computing system, is to provide several servers with a distributed database. For example, in an exemplary distributed computing system using a distributed database with three servers, each of the servers may contain approximately one third of the entire database, and may have a pool of computing nodes connecting to them for computations. In this system, a server A may send and receive tasks to/from a set A of computing nodes, a server B may send and receive tasks to/from a set B of computing nodes, and a server C may send and receive tasks to/from a set C of computing nodes, the sets A, B, and C of computing nodes being disjoint. In this example, the bandwidth required for each of the servers would be one third of the total bandwidth. If the bandwidth per server were identical, this would in effect increase the total number of connections possible for the entire system by a factor of 3.
In networks including, but not limited to, peer-to-peer networks, nodes on the network may go down at any time or lose network connectivity for long periods. For instance, server A in the above example may become unreachable for an indefinite period, in which case one third of the data collected may be effectively lost.
Replicated Databases
Another solution to the reliability and efficiency problems created by having a single centralized server for a database, for example a database in a distributed computing system, is to replicate the entire database across two or more servers on the network. This solution helps to avoid the problem of the potential loss of a portion of a distributed database described above.
In a network, for example a peer-to-peer network, nodes on the network may be unreliable; that is, the nodes may go down or leave the network at any time. Since the nodes are not reliable, a database that resides on a single node (e.g. a peer node, in a peer-to-peer network) becomes unavailable to clients on the network if the node hosting the database (which may be referred to as a server node, server peer, or simply server) goes down. Therefore, in some database systems, the database may be replicated on two or more server nodes that may be, but are not necessarily, located in different geographical locations, so that the loss of one node does not result in the loss of availability of the database. In addition, two or more server nodes that replicate a database may allow the access and processing load on the database to be spread across the server nodes. Different clients may access different copies of the database replicated on the two or more server nodes, which may help to improve the overall performance of the database.
FIG. 2 illustrates an exemplary database 154 replicated across three servers 152 on a network 150. One or more clients 156 may each access a copy of the database 154 (e.g. copy 154A, 154B or 154C) on one of the servers 152 via network 150. Different clients 156 may access different copies of the database 154. Note that servers 152 and clients 156 may be implemented on peer nodes in a peer-to-peer networking environment, or on nodes in other types of networking environments.